/*
希尔排序，也称递减增量排序算法

基本思想：
    先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，
        待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序

具体步骤：
1. 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
2. 按增量序列个数 k，对序列进行 k 趟排序；
3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。
    仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度

最好时间复杂度：O(NlogN)
最坏时间复杂度：O(nlogN)
平均时间复杂度：O(NlogN)
空间复杂度：O(1)

稳定排序:否
原地排序:是

*/
#include "../../include/common.h"

void shell_sort(ElementType arr[], int n) {
        int gap, i, j;
        int temp;
        for (gap = n >> 1; gap > 0; gap >>= 1)  // 分组次数，直到增量为1，即为普通插入排序
            // 每间隔 gap 的构成一组，进行一次插入排序
            for (i = gap; i < n; i++) {     // 每一个元素都参与组内的插入排序
                if (arr[i] < arr[i-gap]){
                    temp = arr[i];
                    for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                            arr[j + gap] = arr[j];
                    arr[j + gap] = temp;
                }
            }
}

/*
 算法实现：不是从头开始，间隔 gap 进行跳跃；而是从 gap 开始，依次和前面 gap 个元素比较
*/


/**
 * 改进：
 *  在扫描分组数据使不必要每次都交换，找到最终的位置直接插入待处理元素即可（类似折半插入）
*/